/*
 * @lc app=leetcode.cn id=864 lang=typescript
 *
 * [864] 获取所有钥匙的最短路径
 */

// @lc code=start
interface Cell {
  x: number;
  y: number;
  step: number;
  status: number;
}

function shortestPathAllKeys(grid: string[]): number {
  const m = grid.length;
  const n = grid[0].length;
  const dirs: number[][] = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
  ];
  const bitMap = [1, 2, 4, 8, 16, 32, 64];
  // 记录访问状态
  const visited = new Array(m)
    .fill(0)
    .map(() => new Array(n).fill(0).map(() => new Array(bitMap[6]).fill(0)));
  // 搜索队列
  const queue: Cell[] = [];
  let keyNumber = 0;
  // 初始化起点
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '@') {
        queue.push({ x: i, y: j, step: 0, status: 0 });
        visited[i][j][0] = 1;
      } else if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
        keyNumber++;
      }
    }
  }
  // 搜索
  while (queue.length) {
    const curr = queue.shift()!;

    // 所有钥匙都获得
    if (curr.status === bitMap[keyNumber] - 1) {
      return curr.step;
    }
    // 扩展下一个状态
    for (const [dx, dy] of dirs) {
      const x = curr.x + dx;
      const y = curr.y + dy;
      if (x < 0 || x >= m) continue;
      if (y < 0 || y >= n) continue;
      if (grid[x][y] === '#') continue;
      if (visited[x][y][curr.status] === 1) continue;
      if (grid[x][y] === '.' || grid[x][y] === '@') {
        visited[x][y][curr.status] = 1;
        queue.push({ x, y, step: curr.step + 1, status: curr.status });
      } else if (grid[x][y] >= 'a' && grid[x][y] <= 'f') {
        visited[x][y][curr.status] = 1;
        // 获得钥匙后的状态也要记录
        const status = curr.status | bitMap[grid[x][y].charCodeAt(0) - 97];
        visited[x][y][status] = 1;
        queue.push({ x, y, step: curr.step + 1, status });
      } else if (
        grid[x][y] >= 'A' &&
        grid[x][y] <= 'F' &&
        curr.status & bitMap[grid[x][y].charCodeAt(0) - 65]
      ) {
        visited[x][y][curr.status] = 1;
        queue.push({ x, y, step: curr.step + 1, status: curr.status });
      }
    }
  }

  return -1;
}
// @lc code=end
